home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / LANG / GOFER / scripts / Modular < prev    next >
Text File  |  1993-11-25  |  2KB  |  61 lines
  1. -------------------- Modular arithmetic --------------------
  2.  
  3. p :: Int
  4. p = 7     -- change this appropriately
  5.  
  6. ----------- Datatypes --------------------
  7.  
  8. data Residue = Res Int
  9.  
  10. ----------- Instance declarations ---------
  11.  
  12. instance Eq Residue where
  13.   (Res x) == (Res y) = (x-y) `mod` p == 0
  14.  
  15. instance Mult Residue where
  16.   unit = Res 1
  17.  
  18. instance LeftMul Residue Residue where
  19.   (Res x) * (Res y) = Res ((x*y) `mod` p)
  20.  
  21. instance LeftMul Int Residue where
  22.     n * (Res x) = (Res n) * (Res x)
  23.  
  24. instance Add Residue where
  25.    (Res x) + (Res y) = Res ((x+y) `mod` p)
  26.    (Res x) - (Res y) = Res ((x-y) `mod` p)
  27.    zero = Res 0
  28.  
  29. instance Div Residue Residue where
  30.    (Res x) / (Res y) = Res ((x*u) `mod` p) where
  31.          (1,u,_) = gcdplus y p
  32.  
  33. instance Div Residue Int where
  34.     x / n  =  x / (Res (n `mod` p))
  35.  
  36.  
  37. --------- Definitions --------------------
  38.  
  39. --- gcdplus x y == (d,u,v) where u*x+v*y == d ( == hcf x y )
  40. gcdplus :: Int -> Int -> (Int,Int,Int)
  41. gcdplus x y | y == 0     = (x, 1, 0)
  42.             | otherwise  = (d, v, u-v*(x/y))
  43.               where (d, u, v) = gcdplus y (x `mod` y)
  44.  
  45. --- x^(order x) == 1 modulo p
  46. order :: Residue -> Int
  47. order x = 1 + length (takeWhile (/= unit) [ x^n | n <- [1..]])
  48.  
  49. --- every x == primGen^n modulo p for some n, if x /= 0 modulo p
  50. primGen :: Residue
  51. primGen = Res g
  52.      where g = while (\x -> (order (Res x) /= (p-1))) (+1) 2
  53.  
  54. length x = sum [ 1 | _ <- x ]
  55.  
  56. while          :: (a -> Bool) -> (a -> a) -> a -> a
  57. while p f x | p x       = while p f (f x)
  58.             | otherwise = x
  59.  
  60. ------ End Modular
  61.